import random
import numpy as np
import math
from math import exp
import matplotlib.pyplot as plt

#31个城市的坐标
city_loc = [(41, 94), (37, 84), (54, 67), (25, 62), (7, 64),
            (2, 2), (68, 50), (71, 60), (54, 62), (83, 69)]

def drawPath(best_path):
    n = len(best_path)
    x = [0 for col in range(n + 1)]
    y = [0 for col in range(n + 1)]

    for i in range(n):
        x[i] = city_loc[best_path[i]][0]
        y[i] = city_loc[best_path[i]][1]
    x[n] = x[0]
    y[n] = y[0]

    print("最佳路线为：")
    for i, city in enumerate(list(zip(x, y))):
        print(city, end=', ')
        if i % 10 == 9:
            print()

    plt.xlim(0, 100)
    plt.ylim(0, 100)
    plt.plot(x, y, marker='o', mec='b', label='path')
    plt.legend()
    plt.xlabel("x")
    plt.ylabel("y")
    plt.title("SA_TSP")
    plt.show()
    opt = 0
    for i in range(len(best_path)):
       opt += dist(best_path[i], best_path[(i + 1) % len(best_path)])
    print(opt)
    print(best_path)
#两个城市的距离
def dist(a, b):
    x1 = city_loc[a][0]
    x2 = city_loc[b][0]
    y1 = city_loc[a][1]
    y2 = city_loc[b][1]
    distance = ((x2 - x1)**2 + (y2 - y1)**2)**0.5
    return distance
#路程总长
def ObjFun(x,n):
    value = 0
    for j in range(n-1):
        value += dist(x[j], x[j + 1])
    value += dist(x[n-1], x[0])
    return value

def init_ans(n):
    ans = []
    for i in range(n):
        ans.append(i)
    return ans
# 生成邻域新解
def Disturbance(x,n):
    xNew = []
    for i in range(len(x)):
        xNew.append(x[i])
    cuta = random.randint(0,n-1)
    cutb = random.randint(0,n-1)
    xNew[cuta], xNew[cutb] = xNew[cutb], xNew[cuta]
    return xNew

def Judge(yNew, y, T):
    if yNew<y:
        return 1
    else:
        if math.exp(-(yNew - y) / T)>random.random():
            return 1
    return 0

def anneal(T,Tmin,epochs,t,n):
    x = init_ans(n)
    trend = []
    while T > Tmin:
        for i in range(epochs):
            xNew = Disturbance(x,n)
            y = ObjFun(x,n)
            if(Judge(ObjFun(xNew,n), y, T)):
                x = xNew
                print(f'本次降温温度：{T},路程最小值：{ObjFun(x,n)}')
        T = T * t
        trend.append(ObjFun(x,n))
    plt.plot(trend)
    plt.show()
    drawPath(x)

T,Tmin = 100,1e-10  # 设置初始温度,最小温度
epochs = 5  # 设置每一次降温后的执行次数
t = 0.99  # 降温函数
anneal(T,Tmin,epochs,t,len(city_loc))


